//============================================================================
// Name        : Bridge2.cpp
// Author      : Xubin
// Version     : Done on 2011.11.6
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#include <stack>

#define MIN(x,y) (x>y ? y : x)
#define MAX(x,y) (x>y ? x : y)

using namespace std;
class ANode;
class BNode;
class Setter;
typedef pair<short, short> PT;
typedef vector<short> VT;
typedef stack<PT> ST;

class People
{
private:
	VT v;
public:
	People() :
		v()
	{
	}
	;
	void push(short i)
	{
		v.push_back(i);
		sort(v.begin(), v.end());
	}
	void erase(short i)
	{
		v.erase(find(v.begin(), v.end(), i));
		sort(v.begin(), v.end());
	}
	short findGreater(const short s)
	{
		VT::iterator i = v.begin();
		while (i != v.end() && *i <= s)
		{
			i++;
		}
		if (i == v.end())
		{
			return 0;
		}
		else
		{
			return *i;
		}
	}
	int size()
	{
		return v.size();
	}
	void print(string s = "")
	{
		cout << s;
		cout << ":";
		VT::const_iterator i = v.begin();
		while (i != v.end())
		{
			cout << *i << ",";
			++i;
		}
		cout << endl;
	}
};

class State
{
public:
	const static int maxSteps = 30;
	int curSteps;
	ST steps;
	State() :
		curSteps(0), steps()
	{
	}
	void printSteps(string str = "")
	{
		ST s(steps);
		cout << str;
		while (!s.empty())
		{
			if (s.top().second != 0)
				cout << " (" << s.top().first << ", " << s.top().second << ") ";
			else
				cout << " (" << s.top().first  << ") ";
			s.pop();
		}
		cout << endl;
	}
};

class Node
{
public:
	PT cancelFromB;
	short cancelFromA;
	Node()
	{
		cancelFromA = 0;
		cancelFromB = make_pair(0, 0);
	}
	Node(short s)
	{
		cancelFromA = s;
		cancelFromB = make_pair(0, 0);
	}
	Node(PT p)
	{
		cancelFromA = 0;
		cancelFromB = p;
	}
	virtual bool nextNode(People &aPeople, People &bPeople, Node &outNode,
			State &state) = 0;
};
class ANode: public Node
{
public:
	ANode() :
		Node()
	{
	}
	ANode(PT p) :
		Node(p)
	{
	}
	bool nextNode(People &aPeople, People &bPeople, Node &outNode, State &state)
	{
		//test
		/*		cout << "ANode:nextNode():" << endl;
		 cout << "  ";
		 aPeople.print("aPeople");
		 cout << "  ";
		 bPeople.print("bPeople");
		 cout << "  " << "cancelFromA:" << cancelFromA << endl;
		 cout << "  " << "cancelFromB:" << cancelFromB.first << ","
		 << cancelFromB.second << endl;*/
		//test
		short i = 0, j = 0;
		j = aPeople.findGreater(MAX(cancelFromB.first, cancelFromB.second));
		i = MIN(cancelFromB.first, cancelFromB.second);
		if (i == 0 || j == 0)
		{
			i = aPeople.findGreater(MIN(cancelFromB.first, cancelFromB.second));
			j = aPeople.findGreater(i);
		}

		if (i == 0 || j == 0 || state.curSteps >= state.maxSteps)
		{// Step Back
			if (aPeople.size() == 5)
			{ // can't step back anymore.
				return false;
			}
			PT p = state.steps.top();
			i = MAX(p.first, p.second);
			state.steps.pop();
			state.curSteps -= i;
			aPeople.erase(i);
			bPeople.push(i);
			//			Setter::setCancelFromA(i, &outNode);
			outNode.cancelFromA = i;
			outNode.cancelFromB = make_pair(0, 0);
		}
		else
		{// Go Forward
			state.steps.push(make_pair(MIN(i,j), MAX(i, j)));
			state.curSteps += MAX(i,j);
			aPeople.erase(i);
			aPeople.erase(j);
			bPeople.push(i);
			bPeople.push(j);
			outNode.cancelFromA = 0;
			outNode.cancelFromB = make_pair(0, 0);
		}
		return true;
	}
};

class BNode: public Node
{
public:
	BNode() :
		Node()
	{
	}
	BNode(short i) :
		Node(i)
	{
	}
	bool nextNode(People &aPeople, People &bPeople, Node &outNode, State &state)
	{
		//test
		/*		cout << "BNode:nextNode():" << endl;
		 cout << "  ";
		 aPeople.print("aPeople");
		 cout << "  ";
		 bPeople.print("bPeople");
		 cout << "  " << "cancelFromA:" << cancelFromA << endl;
		 cout << "  " << "cancelFromB:" << cancelFromB.first << ","
		 << cancelFromB.second << endl;*/
		//test
		int i;
		i = bPeople.findGreater(cancelFromA);
		if (i == 0 || bPeople.size() == 5 || state.curSteps >= state.maxSteps)
		{ // step back
			if (bPeople.size() == 5 && state.curSteps <= state.maxSteps)
			{
				cout<<state.curSteps<<": ";
				state.printSteps();
			}
			PT p = state.steps.top();
			state.steps.pop();
			state.curSteps -= MAX(p.first, p.second);
			aPeople.push(p.first);
			aPeople.push(p.second);
			bPeople.erase(p.first);
			bPeople.erase(p.second);
			//Setter::setCancelFromB(p, &outNode);
			outNode.cancelFromB = p;
			outNode.cancelFromA = 0;
		}
		else
		{ // go ahead
			aPeople.push(i);
			bPeople.erase(i);
			state.steps.push(make_pair(i, 0));
			state.curSteps += i;
			outNode.cancelFromA = 0;
			outNode.cancelFromB = make_pair(0, 0);
		}
		return true;
	}
};

int main()
{
	People aPeople, bPeople;

	ANode aNode;
	BNode bNode;
	bool goon = false;
	State state;
	aPeople.push(1);
	aPeople.push(3);
	aPeople.push(6);
	aPeople.push(8);
	aPeople.push(12);
	while (1)
	{
		goon = aNode.nextNode(aPeople, bPeople, bNode, state);
		if (!goon)
		{
			cout << "-------Finished--------" << endl;
			break;
		}
		goon = bNode.nextNode(aPeople, bPeople, aNode, state);
		if (!goon)
		{
			cout << "-------Finished--------" << endl;
			break;
		}
	}

	return 0;
}
